package algorithme;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;

public class Rouxov_Sivadov extends Boruvka {
	private int N;

	public Rouxov_Sivadov(int n) {
		this.N = n;
	}

	public Graphe appliquer(Graphe graphe) {
		List<Arete> aretes = new ArrayList<Arete>(graphe.getAretes());
		List<Arete> l = new ArrayList<Arete>();
		Map<Arete, Arete> aretes_originales = pondererAretes(aretes, l);

		Graphe r = doRouxovSivadov(new Graphe(l));
		Graphe result = new Graphe();
		for (Arete a : r.getAretes())
			result.ajouterArete(aretes_originales.get(a));
		return result;
	}

	public Graphe doRouxovSivadov(Graphe g) {
		List<Arete> acpm = new ArrayList<Arete>();
		List<Arete> acpm_tmp = new ArrayList<Arete>();
		Set<Integer> sommets_dispos = new HashSet<Integer>(g.getSommets());
		Graphe g_next = new Graphe(g);

		while (g.nbSommets() > 1) {
			while (!sommets_dispos.isEmpty()) {
				// on extrait du graphe un groupe de 2^N sommets
				Collection<Integer> groupe = makeGroup(g, (int)Math.pow(2, N), sommets_dispos);

				// on créé un graphe G0i contenant ces sommets et leurs arêtes
				Graphe mini = new Graphe();
				for (int i : groupe)
					mini.ajouterAretes(g.getAretesAdjacentes(i));
				// on applique N phases de boruvka sur G0i => au plus N arêtes
				// de l'acpm
				for (int i = 0; i < N && mini.nbSommets() > 1; ++i)
					phaseBoruvka(mini, acpm_tmp);

				// on créé G1 contenant un sommet par groupe de G, et contenant
				// toutes les arêtes d'un groupe à l'autre
				for (Arete a : acpm)
					g_next.unir(a);
				acpm.addAll(acpm_tmp);
				acpm_tmp.clear();

				// on itère jusqu'à avoir regroupé tous les sommets de G
			}

			// on itère la procédure sur G1 au lieu de G tant que le graphe
			// contient plus d'un sommet
			g = g_next;
		}

		return new Graphe(acpm);
	}

	private Collection<Integer> makeGroup(Graphe g, int size,
			Set<Integer> sommets_dispos) {
		Random rand = new Random();
		Set<Integer> groupe = new HashSet<Integer>(size);

		int sommet_choisi = -1;

		Arete arete_choisie;
		List<Arete> aretesdispo = new ArrayList<Arete>(size);

		// choix d'un sommet de départ au hasard dans G -> groupe de sommets
		// actuel
		while (sommet_choisi < 0) {
			// FIXME : choix pas très aléatoire, mais impossible
			sommet_choisi = sommets_dispos.iterator().next();
			sommet_choisi = choisir_sommet(groupe, sommet_choisi,
					sommets_dispos);
		}

		aretesdispo.addAll(g.getAretesAdjacentes(sommet_choisi));
		while (groupe.size() < size && aretesdispo.size() > 0) {
			// à partir du groupe actuel, on choisit au hasard une arête sortant
			// du groupe
			boolean test = false;
			while (!test && aretesdispo.size() > 0) {
				arete_choisie = aretesdispo
						.remove(rand.nextInt(aretesdispo.size()));
				// on ajoute le sommet de destination au groupe
				sommet_choisi = (arete_choisie.getU() == sommet_choisi) ? arete_choisie
						.getV()
						: arete_choisie.getU();
				test = choisir_sommet(groupe, sommet_choisi, sommets_dispos) != -1;
				aretesdispo.remove(arete_choisie);
			}
			
			aretesdispo.addAll(g.getAretesAdjacentes(sommet_choisi));
			groupe.add(sommet_choisi);
		}

		return groupe;
	}

	private static int choisir_sommet(Collection<Integer> groupe,
			int sommet_choisi, Set<Integer> sommets_dispos) {
		if (sommets_dispos.contains(sommet_choisi)) {
			groupe.add(sommet_choisi);
			sommets_dispos.remove(sommet_choisi);
			return sommet_choisi;
		} else
			return -1;
	}

	public String getName() {
		return "Rouxov - Sivadov";
	}

}
